package Tree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 *
 * 这个注意输入已经是二叉搜索树了
 */
public class L173_二叉搜索树迭代器 {
}

class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        leftMostInorder(root);
    }

    //先只处理左边，这样内存就实际只使用树的高度
    private void leftMostInorder(TreeNode root){
        while (root != null){
            stack.push(root.left);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        //按照顺序左边陷进去，然后，出来后，把右子树放进去
        TreeNode node = stack.pop();
        leftMostInorder(node.right);
        return node.val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return stack.size() > 0;
    }

}
